package com.future;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Description: 5. 最长回文子串
 *
 * @author weiruibai.vendor
 * Date: 2022/7/29 09:57
 */
public class Solution_5 {

    public static void main(String[] args) {
        Solution_5 solution = new Solution_5();
        String s = "babad";
        s = "cbbd";
        // s = "aabaadefabcdcba";
        //s = "babad";
        System.out.println(solution.longestPalindrome(s));
        System.out.println(solution.longestPalindrome_dp(s));
    }

    public String longestPalindrome_dp(String s) {
        if (s.length() == 1) {
            return s;
        }
        int N = s.length();
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            if (i != N - 1 && chars[i] == chars[i + 1]) {
                dp[i][i + 1] = true;
            }
            dp[i][i] = true;
        }
        int longest = 0;
        int L = 0;
        int R = 0;
        for (int i = N - 3; i >= 0; i--) {
            for (int j = i + 2; j < N; j++) {
                if (chars[i] == chars[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (dp[i][j] && (j - i > R - L)) {
                    L = i;
                    R = j;
                }
            }
        }
        return s.substring(L, R + 1);
    }

    public String longestPalindrome(String s) {
        if (s.length() == 1) {
            return s;
        }
        String ans = "";
        int[] indexs = new int[2];
        char[] chars = s.toCharArray();
        Map<Character, List<Integer>> charIndexMap = new HashMap<>();
        buildCharIndexMap(charIndexMap, chars);
        Set<Character> repeat = new HashSet<>();
        for (Character cha : chars) {
            int[] tmpIndexs;
            if (repeat.add(cha)) {
                List<Integer> list = charIndexMap.get(cha);
                int size = list.size();
                for (int i = 0; i < size; i++) {
                    if (size == 1) {
                        // 向两边扩张
                        tmpIndexs = expand(chars, list.get(0) - 1, list.get(0) + 1);
                        if (indexs[1] - indexs[0] < tmpIndexs[1] - tmpIndexs[0]) {
                            indexs = tmpIndexs;
                        }
                    } else {
                        int L = list.get(i);
                        for (int j = i + 1; j < size; j++) {
                            Integer R = list.get(j);
                            /**
                             * L....R之间是否是回文
                             */
                            tmpIndexs = shrinkSides(chars, L, R);
                            if (indexs[1] - indexs[0] < tmpIndexs[1] - tmpIndexs[0]) {
                                indexs = tmpIndexs;
                            }
                        }
                    }
                }
            }
        }
        return s.substring(indexs[0], indexs[1] + 1);
    }

    /**
     * 从l...r向中点收缩
     *
     * @param chars
     * @param l
     * @param r
     * @return
     */
    private int[] shrinkSides(char[] chars, int l, Integer r) {
        int L = l;
        int R = r;
        while (L < R) {
            if (chars[L] != chars[R]) {
                return new int[]{0, 0};
            }
            L++;
            R--;
        }
        return new int[]{l, r};
    }

    /**
     * 两边扩展
     *
     * @param chars
     * @param L
     * @param R
     * @return
     */
    private int[] expand(char[] chars, Integer L, Integer R) {
        if (L < 0 || R >= chars.length || chars[L] != chars[R]) {
            return new int[]{L + 1, R - 1};
        }
        return expand(chars, L - 1, R + 1);
    }

    private void buildCharIndexMap(Map<Character, List<Integer>> charIndexMap, char[] chars) {
        for (int i = 0; i < chars.length; i++) {
            List<Integer> list = charIndexMap.getOrDefault(chars[i], new ArrayList<>());
            list.add(i);
            charIndexMap.put(chars[i], list);
        }
    }

}
